package leetcode_day._2022._202209._1120;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 827. 最大人工岛
 * 算法：深度优先搜索
 *
 * @author yzh
 * @version 1.0
 * @date 2022/9/18 21:50
 */
public class _18 {

    public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0) return 1;
        int ans = 0, m = grid.length, n = grid[0].length, idx = 2;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) if (grid[i][j] == 1) map.put(idx, getArea(grid, i, j, idx++));
        // 一个岛屿也没有
        if (map.size() == 0) return 1;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> set = getIsLand(grid, i, j);
                    if (set.size() == 0) continue;
                    ans = Math.max(ans, set.stream().map(v -> map.get(v)).reduce(Integer::sum).orElse(0) + 1);
                }
            }
        // 全部都是岛屿
        if (ans == 0) return map.get(2);
        return ans;
    }

    int getArea(int[][] grid, int r, int c, int idx) {
        if (!isLegal(grid, r, c) || grid[r][c] != 1) return 0;
        grid[r][c] = idx;
        return getArea(grid, r + 1, c, idx) + getArea(grid, r - 1, c, idx)
                + getArea(grid, r, c + 1, idx) + getArea(grid, r, c - 1, idx) + 1;
    }

    Set<Integer> getIsLand(int[][] grid, int r, int c) {
        Set<Integer> res = new HashSet<>();
        if (isLegal(grid, r + 1, c) && grid[r + 1][c] != 0) res.add(grid[r + 1][c]);
        if (isLegal(grid, r - 1, c) && grid[r - 1][c] != 0) res.add(grid[r - 1][c]);
        if (isLegal(grid, r, c + 1) && grid[r][c + 1] != 0) res.add(grid[r][c + 1]);
        if (isLegal(grid, r, c - 1) && grid[r][c - 1] != 0) res.add(grid[r][c - 1]);
        return res;
    }

    boolean isLegal(int[][] grid, int r, int c) {
        return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length;
    }

}
